#include<cstdio>

long long quickpow(int m,int n,int k)
{
	long long b=1;
	while(n>0)
	{
		if(n&1)b=(b*m)%k;
		n=n>>1;
		m=((long long)m*m)%k;
	}
	return b;
}

int cas,h,mod;

int main()
{
	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&mod,&h);
		long long ans=0;
		for(int i=1;i<=h;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			ans=(ans+quickpow(a,b,mod))%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
